// 47. 全排列II
// https://leetcode.cn/problems/permutations-ii/

/**
示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
    let ret = []; // 用于存储所有的组合方式，一种组合记录一个
    nums.sort((a, b) => a - b);

    for (let i = 0; i < nums.length; i++) {
        if (i >= 1 && nums[i] === nums[i - 1]) {
            continue;
        }
        dfs([].concat(nums), nums.length, i, 0, [], ret);
    }

    console.table(ret);
    return ret;
};

/**
 * 返回数组arr的全排列
 * @param {*} arr 当前可用数组成的数组，排列每经过一层，都会失去一个元素
 * @param {*} max 递归总层数
 * @param {*} index 根节点index
 * @param {*} level 递归当前所处的层数
 * @param {*} acc 当前排列的数组
 * @param {*} allArrangement 存储所有的组合方式，一种组合记录一个
 * @returns
 */
function dfs(arr, max, index, level, acc, allArrangement) {
    if (acc.length == max || level === max) {
        allArrangement.push(acc);
        return;
    }

    acc.push(arr[index]);
    arr.splice(index, 1);

    // 全排列或者数组到底了
    if (arr.length === 0 && acc.length === max) {
        allArrangement.push(acc);
        return;
    }

    for (let i = 0; i < arr.length; i++) {
        if (i >= 1 && arr[i] === arr[i - 1]) {
            continue;
        }

        dfs([].concat(arr), max, i, level + 1, [].concat(acc), allArrangement);
    }
}

permuteUnique([2, 1, 1]); // [[1,1,2],[1,2,1],[2,1,1]]
permuteUnique([2, 1, 3]); // [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
